#include "adjacencestructgraph.h"
#include "setgraph.h"
#include "adjacencematrix.h"
#include "incidencematrixgraph.h"

// implementações "tunadas"
#include "altadjacencestructgraph.h"
#include "altsetgraph.h"

#include "graphprinter.h"

#include "algorithms.h"

#include <iostream>
#include <string>
#include <assert.h>

using namespace std;

template<typename G>
void createAndTestGraph(G &graph)
{
  int n1 = graph.addNode(17);
  int n2 = graph.addNode(35);
  int n3 = graph.addNode(42);
  int n4 = graph.addNode(69);

  assert(n1 == 0);
  assert(n2 == 1);
  assert(n3 == 2);
  assert(n4 == 3);

  assert(graph.addEdge(n1,n2,"Leandro"));
  assert(graph.addEdge(n1,n3,"Kelyane"));
  assert(graph.addEdge(n1,n4,"Maria"));
  assert(graph.addEdge(n2,n3,"José"));
  assert(graph.addEdge(n2,n4,"Zilda"));

  // uma inserção errada
  assert(!graph.addEdge(400,500));

  // uma inserção de um  loop
  assert(!graph.addEdge(n2,n2));

  assert(graph.getNodeDegree(n1) == 3);
  assert(graph.getNodeDegree(n2) == 3);
  assert(graph.getNodeDegree(n3) == 2);
  assert(graph.getNodeDegree(n4) == 2);

  assert(graph.areNodesAdjacents(n1,n2));
  assert(graph.areNodesAdjacents(n1,n3));
  assert(graph.areNodesAdjacents(n1,n4));
  assert(graph.areNodesAdjacents(n2,n3));
  assert(graph.areNodesAdjacents(n2,n4));

  assert(graph.areNodesAdjacents(n2,n1));
  assert(graph.areNodesAdjacents(n3,n1));
  assert(graph.areNodesAdjacents(n4,n1));
  assert(graph.areNodesAdjacents(n3,n2));
  assert(graph.areNodesAdjacents(n4,n2));

  assert(!graph.areNodesAdjacents(n3,n4));
  assert(!graph.areNodesAdjacents(n4,n3));

  assert(graph.getEdgeValue(n1,n2) == "Leandro");
  assert(graph.getEdgeValue(n1,n3) == "Kelyane");
  assert(graph.getEdgeValue(n1,n4) == "Maria");
  assert(graph.getEdgeValue(n2,n3) == "José");
  assert(graph.getEdgeValue(n2,n4) == "Zilda");

  assert(graph.getEdgeValue(n2,n1) == "Leandro");
  assert(graph.getEdgeValue(n3,n1) == "Kelyane");
  assert(graph.getEdgeValue(n4,n1) == "Maria");
  assert(graph.getEdgeValue(n3,n2) == "José");
  assert(graph.getEdgeValue(n4,n2) == "Zilda");

  assert(graph.getEdgeValue(n2,n4) != "Leandro");
  assert(graph.getEdgeValue(n4,n2) != "Leandro");

  assert(graph.getNodeValue(n1) == 17);
  assert(graph.getNodeValue(n2) == 35);
  assert(graph.getNodeValue(n3) == 42);
  assert(graph.getNodeValue(n4) == 69);

  assert(graph.getAdjacentNodes(n1) == vector<int>({n2,n3,n4}));
  assert(graph.getAdjacentNodes(n2) == vector<int>({n1,n3,n4}));
  assert(graph.getAdjacentNodes(n3) == vector<int>({n1,n2}));
  assert(graph.getAdjacentNodes(n4) == vector<int>({n1,n2}));

  assert(graph.getAdjacentNodes(n4) != vector<int>({n1,n2,n3,n4}));

  assert(graph.countNodes() == 4);
  assert(graph.countEdges() == 5);
  
  vector<int> s = bfs<G>(graph,0);

  assert(s.size() == 4);
}

// cria um grafo mais complexo, que será usado na busca por articulações e largura
template<typename G>
void createGraph2(G &graph)
{
  // grafo exemplo do material (1a)
  for (int i = 1; i<=8; i++) {
    graph.addNode(i);
  }

  vector<pair<int,int>> edges {
    {1,2},
    {1,3},
    {2,5},
    {2,4},
    {5,4},
    {3,4},
    {4,6},
    {6,7},
    {7,8},
    {6,8}
  };

  for (auto e: edges) {
    graph.addEdge(e.first -1  ,e.second -1); // -1 pois a representação usa 0 como primeiro elemento    
  }
}

template<typename G>
void searchArticulationTest(const G &graph)
{
  // as articulações são os vértices 4 e 6 ()
  vector<int> expectedArticulations {4 -1, 6 -1};

  // para todas as possíveis árvores, o resultado deve ser o mesmo
  for (int i = 0; i < graph.countNodes(); i++) {
    vector<int> gotArticulations = ArticulationSearch<G>(graph).getArticulations(i);
    sort(gotArticulations.begin(), gotArticulations.end());
    assert(gotArticulations == expectedArticulations);
  }
}

void testAdjacenceStruct()
{
  AdjacenceStructGraph<int,string> graph;
  createAndTestGraph<AdjacenceStructGraph<int,string>>(graph);

  {
    AdjacenceStructGraph<> graph;
    createGraph2<AdjacenceStructGraph<>>(graph);
    searchArticulationTest<AdjacenceStructGraph<>>(graph);
  }
}

void testAltAdjacenceStruct()
{
  AltAdjacenceStructGraph<int,string> graph;
  createAndTestGraph<AltAdjacenceStructGraph<int,string>>(graph);

  {
    AltAdjacenceStructGraph<> graph;
    createGraph2<AltAdjacenceStructGraph<>>(graph);
    searchArticulationTest<AltAdjacenceStructGraph<>>(graph);
  }
}

void testSet()
{
  SetGraph<int,string> graph;
  createAndTestGraph<SetGraph<int,string>>(graph);

  {
    SetGraph<> graph;
    createGraph2<SetGraph<>>(graph);
    searchArticulationTest<SetGraph<>>(graph);
  }
}

void testAltSet()
{
  AltSetGraph<int,string> graph;
  createAndTestGraph<AltSetGraph<int,string>>(graph);

  {
    AltSetGraph<> graph;
    createGraph2<AltSetGraph<>>(graph);
    searchArticulationTest<AltSetGraph<>>(graph);
  }
}

void testAdjacenceMatrix()
{
  AdjacenceMatrixGraph<int,string> graph(4);
  createAndTestGraph<AdjacenceMatrixGraph<int,string>>(graph);

  {
    AdjacenceMatrixGraph<> graph(8);
    createGraph2<AdjacenceMatrixGraph<>>(graph);
    searchArticulationTest<AdjacenceMatrixGraph<>>(graph);
  }
}

void testIncidenceMatrix()
{
  IncidenceMatrixGraph<int,string> graph(4);
  createAndTestGraph<IncidenceMatrixGraph<int,string>>(graph);

  {
    IncidenceMatrixGraph<> graph(8);
    createGraph2<IncidenceMatrixGraph<>>(graph);
    searchArticulationTest<IncidenceMatrixGraph<>>(graph);
  }
}

int main()
{
  testAdjacenceStruct(); // ok
  testSet(); // ok
  testAdjacenceMatrix(); // ok
  testIncidenceMatrix(); // ok
  testAltSet(); // ok
  testAltAdjacenceStruct(); // ok
}
